package J20250121_Dynamic;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:动态规划31——33
 * User: 王圆豪
 * Date: 2025-01-23
 * Time: 23:27
 */
public class Solution3 {
    //最⻓等差数列--https://leetcode.cn/problems/longest-arithmetic-subsequence/
    public int longestArithSeqLength(int[] nums) {
        int m = nums.length;
        int[][] dp = new int[m][m];
        int ret = 2;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < m; j++){
                dp[i][j] = 2;
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = i+1; j < m; j++){
                int k = 2*nums[i] - nums[j];
                int v = map.getOrDefault(k, -1);
                if(v < i && v != -1){
                    dp[i][j] = dp[v][i] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
            map.put(nums[i], i);

        }
        return ret;
    }
    //最⻓的斐波那契⼦序列的⻓度--https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/
    public int lenLongestFibSubseq(int[] arr) {
        int m = arr.length;
        int[][] dp = new int[m][m];
        int ret = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0;i < m; i++){
            map.put(arr[i],i);
        }
        for(int i = 0; i < m; i++){
            for(int j = 0;j < m; j++){
                dp[i][j] = 2;
            }
        }
        for(int i = 1;i < m; i++){
            for(int j = i + 1; j < m; j++){
                int tmp = arr[j] - arr[i];
                int pos = map.getOrDefault(tmp, -1);
                if(pos != -1 && pos < i){
                    dp[i][j] = dp[pos][i] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
        }
        return ret;
    }
    //最长定差子序列——https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/
    public int longestSubsequence(int[] arr, int difference) {
        int m = arr.length;
        int ret = 1;
        int[] dp = new int[m];
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < m; i++) dp[i] = 1;
        map.put(arr[0],1);
        for(int i = 1; i < m; i++){
            dp[i] = map.getOrDefault(arr[i] - difference, 0) + 1;
            map.put(arr[i], dp[i]);
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }
}
